package lc;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Queue;

public class WordLadder {
	private LinkedHashSet<String> visited = new LinkedHashSet<String>();
	
    public int ladderLength(String start, String end, HashSet<String> dict) {
    	visited.clear();
    	LinkedHashMap<String, Integer> depth = new LinkedHashMap<String, Integer>();
    	
    	Queue<String> queue = new LinkedList<String>();
    	queue.offer(start);
    	visited.add(start);
    	
    	depth.put(start, 1);
    	while (!queue.isEmpty()) {
    		String head = queue.poll();
    		
    		if (canBeNext(head, end)) {
    			return depth.get(head)+1;
    		}
    		
    		LinkedList<String> nextWords = nextWords(head, dict);
    		System.out.println(nextWords);
    		for (String item : nextWords) {
    			queue.offer(item);
    			depth.put(item, depth.get(head)+1);
    			if (canBeNext(item, end)) {
    				return depth.get(item)+1;
    			}    			
    		}
    	}
    	
    	return 0;
    }
    
	LinkedList<String> nextWords(String start, HashSet<String> dict) {
		LinkedList<String> result = new LinkedList<String>();
		for (int i = 0; i < start.length(); i++) {
			char[] charArray = start.toCharArray();
			char curr = charArray[i];
			for (char c = 'a'; c <= 'z'; c++) {
				if (c == curr) {
					continue;
				}
				
				charArray[i] = c;
				String string = new String(charArray);
				if (dict.contains(string) && !visited.contains(string)) {
					visited.add(string);
					result.add(string);
				}
			}
		}
		return result;
	}
    
    boolean canBeNext(String start, String end) {
    	int count = 0;
    	for (int i=0; i<start.length(); i++) {
    		if (start.charAt(i) != end.charAt(i)) {
    			count++;
    		}
    	}
    	return count == 1;
    }

    public static void main(String ...strings) {
    	WordLadder sol = new WordLadder();
    	String [] dict1 = {"hot", "dog"};
    	int ladderLength = sol.ladderLength("hot", "dog", new HashSet<String>(Arrays.asList(dict1)));
    	System.out.println(ladderLength);

    	String [] dict2 = {"lest","leet","lose","code","lode","robe","lost"};
    	ladderLength = sol.ladderLength("leet", "code", new HashSet<String>(Arrays.asList(dict2)));
    	System.out.println(ladderLength);

    	String [] dict3 = {"miss","dusk","kiss","musk","tusk","diss","disk","sang","ties","muss"};
    	ladderLength = sol.ladderLength("kiss", "tusk", new HashSet<String>(Arrays.asList(dict3)));
    	System.out.println(ladderLength);
    }
}
